4831. Рюкзак

Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью s, если имеются n золотых слитков с заданными весами.

Вход. Первая строка содержит одно целое число s (1 ≤ s ≤ 10⁴) – вместительность рюкзака. Далее следуют n (1 ≤ n ≤ 300) неотрицательных целых чисел, не превосходящих 10⁵ – веса слитков.

Выход. Выведите максимальный вес золота, который можно унести в рюкзаке.

Пример входа	Пример выхода
20 5 7 12 18	19

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Заведем массив m, в котором m[i] установим в 1, если можно набрать вес в точности i имеющимися слитками. Изначально положим m[0] = 1.

Пусть массив m уже заполнен требуемым образом для некоторого множества слитков. Приходит следующий слиток веса w. Тогда следует положить равным 1 все такие m[i] (w ≤ i ≤ s), для которых m[i – w] = 1.

Ответом будет наибольший вес, не больший s, который можно унести в рюкзаке.

Пример

Для заданного примера максимальный вес 19 достигается для подмножества {7, 12}.

Заполнение ячеек массива m с приходом очередного слитка. Слева указаны массы слитков.

Реализация алгоритма

Объявим рабочий массив.

#define MAX 10010

int m[MAX];

Читаем входные данные.

scanf("%d",&s);

Инициализация массива m.

memset(m,0,sizeof(m));

m[0] = 1;

Обрабатываем очередной слиток весом w. Проходим по массиву m справа налево и устанавливаем в 1 все такие m[i] (w ≤ i ≤ s), для которых m[i – w] = 1.

while(scanf("%d",&w) == 1)

{

for(i = s; i >= w; i--)

if (m[i - w] == 1) m[i] = 1;

}

Ищем наибольший вес, не больший s, который можно унести в рюкзаке, и выводим его.

for(i = s;; i--)

if (m[i] > 0) break;

printf("%d\n",i);

Реализация алгоритма – bitset

#include <cstdio>

#include <cstring>

#include <bitset>

#define MAX 10010

using namespace std;

bitset<MAX> m;

int i, s, w;

int main(void)

{

scanf("%d", &s);

m[0] = 1;

while (scanf("%d", &w) == 1)

{

for (i = s; i >= w; i--)

if (m[i - w] == 1) m[i] = 1;

}

for (i = s;; i--)

if (m[i] > 0) break;

printf("%d\n", i);

}